#pragma once
#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<algorithm>
using namespace std;

class Solution {
public:
    bool vis[51][51] = { 0 };
    int bfs(vector<vector<int>>& f, int bx, int by, int x, int y) {
        if (bx == x && by == y) return 0;
        memset(vis, 0, sizeof(vis));
        int step = 0;
        queue<pair<int, int>> Q;
        Q.emplace(bx, by);
        vis[bx][by] = true;
        int dics[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
        while (Q.size()) {
            ++step;
            int sz = Q.size();
            while (sz--) {
                auto [a, b] = Q.front();
                Q.pop();
                for (auto dic : dics) {
                    int i = a + dic[0], j = b + dic[1];
                    if (i >= 0 && i < f.size() && j >= 0 && j < f[0].size() && f[i][j] && !vis[i][j]) {
                        if (i == x && j == y) return step;
                        vis[i][j] = true;
                        Q.emplace(i, j);
                    }
                }
            }
        }
        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) {
        int m = forest.size(), n = forest[0].size();
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (forest[i][j] > 1) trees.emplace_back(i, j);
        sort(trees.begin(), trees.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2) {
            return forest[p1.first][p1.second] < forest[p2.first][p2.second];
            });
        int bx = 0, by = 0;
        int ret = 0;
        for (auto& [x, y] : trees) {
            int step = bfs(forest, bx, by, x, y);
            if (step == -1) return -1;
            ret += step;
            bx = x, by = y;
        }
        return ret;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vis;
        unordered_set<string> hash(wordList.begin(), wordList.end());
        if (!hash.count(endWord)) return 0;
        queue<string> Q;
        Q.push(beginWord);
        vis.insert(beginWord);
        int step = 0;
        while (Q.size()) {
            ++step;
            int sz = Q.size();
            while (sz--) {
                string cur = Q.front();
                Q.pop();
                for (int i = 0; i < cur.size(); ++i) {
                    string tmp = cur;
                    for (char c = 'a'; c <= 'z'; ++c) {
                        tmp[i] = c;
                        if (tmp == endWord) return step + 1;
                        if (!vis.count(tmp) && hash.count(tmp)) {
                            Q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }

    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> gset(bank.begin(), bank.end());
        queue<string> Q;
        string gene = "ACGT";
        unordered_set<string> gmap;
        Q.push(startGene);
        gmap.insert(startGene);
        int step = 0;
        while (Q.size())
        {
            ++step;
            int sz = Q.size();
            for (int j = 0; j < sz; ++j)
            {
                string cur = Q.front();
                Q.pop();
                for (int i = 0; i < 8; ++i)
                {
                    string tmp = cur;
                    for (int k = 0; k < 4; ++k)
                    {
                        tmp[i] = gene[k];
                        if (gset.find(tmp) == gset.end() || gmap.count(tmp))
                            continue;
                        if (tmp == endGene) return step;
                        Q.push(tmp);
                        gmap.insert(tmp);
                    }
                }
            }
        }
        return -1;
    }

    bool visited[101][101] = { 0 };
    queue<pair<int, int>> Q;
    int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
        int m = maze.size(), n = maze[0].size();
        visited[e[0]][e[1]] = true;
        Q.emplace(e[0], e[1]);
        int step = 0;
        int dics[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };
        while (Q.size())
        {
            ++step;
            int sz = Q.size();
            for (int k = 0; k < sz; ++k)
            {
                auto [i, j] = Q.front();
                Q.pop();
                for (auto dic : dics)
                {
                    int x = i + dic[0], y = j + dic[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && maze[x][y] == '.')
                    {
                        if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;
                        Q.emplace(x, y);
                        visited[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

    int check(int n)
    {

        vector<int> nums;
        while (n > 0)
        {
            nums.push_back(n % 10);
            n /= 10;
        }

        for (int k = 0; k < nums.size(); ++k)
        {
            for (int z = 0; z < nums.size(); ++z)
            {
                if (k != z && nums[k] != 0)
                {
                    int num = nums[k] * 10 + nums[z];
                    if (isPrime(num)) return 1;
                }
            }
        }
        return 0;
    }

    bool isPrime(int n)
    {
        if (n < 2) return false;

        for (int i = 2; i <= sqrt(n); ++i)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

    int magicNum(int a,int b)
    {
        int ans = 0;
        for (int i = a; i <= b; ++i)
        {
            ans+=check(i);
        }
        return ans;
    }
};
